Cooley-Tukey Algorithm
DFTが$ O(N^2)で計算できるのに対して、Cooley-Tukey FFTは$ O(N \log N)で計算できる
やり方
まず、通常のDFT
$ W_N = \exp \left( -i \frac{2 \pi}{N} \right)とするとき、
$ F[k] = \sum_{n=0}^{N-1} f[n] W_N^{kn}
これを$ 2k・$ 2k+1で分ける
$ \begin{aligned} F[2k] =& \sum_{n=0}^{N-1} f[n] W_N^{2kn} \\ =& \sum_{n=0}^{N-1} f[n] W_{N/2}^{kn} \\ =& \sum_{n=0}^{N/2-1} f[n] W_{N/2}^{kn} + \sum_{n=0}^{N/2-1} f[n + N/2] W_{N/2}^{k(n+N/2)} \\ =& \sum_{n=0}^{N/2-1} (f[n] + f[n + N/2]) W_{N/2}^{kn} \end{aligned}
$ W_{N/2}^{k(n + N/2)}は$ W_{N/2}^{kn} W_{N/2}^{(N/2)k}とすることができ、
$ W_{N/2}^{(N/2)k}は$ 1のため破壊できる
同様に、
$ \begin{aligned} F[2k+1] =& \sum_{n=0}^{N-1} f[n] W_N^{(2k+1)n} \\ =& \sum_{n=0}^{N-1} f[n] W_{N}^{n} W_{N/2}^{kn} \\ =& \sum_{n=0}^{N/2-1} f[n] W_N^n W_{N/2}^{kn} + \sum_{n=0}^{N/2-1} f[n + N/2] W_N^{n+N/2} W_{N/2}^{k(n+N/2)} \\ =& \sum_{n=0}^{N/2-1} (f[n] - f[n + N/2]) W_N^n W_{N/2}^{kn} \end{aligned}
$ W_{N}^{n+N/2}は$ W_{N}^{n} W_{N}^{N/2}とすることができ、
$ W_{N}^{N/2}は$ -1のため、符号がひっくり返る
結局、$ W_N^{n+N/2} W_{N/2}^{k(n+N/2)} = -W_N^n W_{N/2}^{kn}
$ F[2k] ・$ F[2k+1] のいずれも、DFTの形になっている
以下の2数列を作って、DFTして、最後に偶数→奇数で噛み合わせ直せばおｋ
$ f_0'[n] = f[n] + f[n+N/2]
$ f_1'[n] = (f[n] - f[n+N/2]) W_N^n
バタフライ演算
DFTのサイズを小さくするために、上記の偶奇で配列を2つに分けるのを再帰的に行っていく
これをバタフライ演算という
https://gyazo.com/32e8fb95988102ddf7e3e2d50eb93ed5
これを再帰でやると結構スタックが深くなってしまう
そこで、ビット逆転を用いて最適化をしてやる